package com.zk.algorithm;

import com.zk.algorithm.bean.TreeNode;
import com.zk.algorithm.sort.QuickSort;

import java.util.ArrayList;
import java.util.List;

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {

    public int kthSmallest(TreeNode root, int k) {
        List<Integer> list = new ArrayList<>();
        inOrder(list, root);

        // ======================
        // BUG: 不能这样写
        // ======================
//        int[] nums = new int[list.size()];
//        list.toArray(nums);
        int[] nums = toIntArray(list);

        return nums[findKthLargest3(nums, k)];
    }

    public static int[] toIntArray(List<Integer> list) {
        int[] ints = new int[list.size()];
        int i = 0;

        for (Integer n : list) {
            ints[i++] = n.intValue();
        }

        return ints;
    }

    private void inOrder(List<Integer> list, TreeNode root) {
        if (root != null) {
            inOrder(list, root.left);
            list.add(root.val);
            inOrder(list, root.right);
        }
    }

    public int findKthLargest3(int[] nums, int k) {
        k = nums.length - k;

        int lo = 0;
        int hi = nums.length - 1;

        while (lo < hi) {
            final int j = QuickSort.partition(nums, lo, hi);

            // ==================================================
            //                     j           k
            //                     ↓           ↓
            // [小于 nums[j] 的| nums[j] |大于 nums[j] 的]
            // ==================================================
            if (j < k) {
                lo = j + 1;
            } else if (j > k) {
                // ==================================================
                //         k           j
                //         ↓           ↓
                // [小于 nums[j] 的| nums[j] |大于 nums[j] 的]
                // ==================================================
                hi = j - 1;
            } else {
                break;
            }
        }

        return nums[k];
    }

}